package leetcode.primary;

public class T79 {
    boolean[][] book;
    public boolean exist(char[][] board, String word) {
        book = new boolean[board.length][board[0].length];
        for (int i=0;i<board.length;i++){
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j]==word.charAt(0)){
                    book[i][j]=true;
                    if (dfs(board,word,i,j,1)){
                        System.out.println("进入dfs方法");
                        return true;
                    }
                    book[i][j]=false;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board,String word,int x,int y,int point){
        if (point==word.length()){
            return true;
        }
        boolean up=false,down=false,left = false,right=false;
        //上
        if (x>0 && board[x-1][y]==word.charAt(point) && !book[x - 1][y]){
            book[x-1][y] = true;
            up = dfs(board,word,x-1,y,point+1);
            book[x-1][y] = false;
        }

        //下
        if(x+1<board.length && board[x+1][y]==word.charAt(point) && !book[x+1][y]){
            book[x+1][y] = true;
            down = dfs(board,word,x+1,y,point+1);
            book[x+1][y] = false;
        }

        //左
        if (y>0 && board[x][y-1]==word.charAt(point)&& !book[x ][y-1]){
            book[x][y-1] = true;
            left=dfs(board,word,x,y-1,point+1);
            book[x][y-1] = false;
        }

        //右
        if (y+1<board[0].length && board[x][y+1]==word.charAt(point)&& !book[x][y+1]){
            book[x][y+1] = true;
            right = dfs(board,word,x,y+1,point+1);
            book[x][y+1] = false;
        }

        if (up || down || left || right){
            System.out.println("x="+x+",y="+y+",char="+word.charAt(point));
        }
        return (up || down || left || right);
    }

    public static void main(String[] args) {
        T79 test = new T79();
        boolean exist = test.exist(new char[][]{{'a','a'}}, "aaa");
        System.out.println(exist);
    }
}
